1. Field of the Invention:
This method and apparatus of the present invention relates to the field of computer graphics more specifically, it relates to the rendering of volume data on a computer display.
2. Art Background:
The technique of rendering volumes, that is data having three dimensional aspects, is frequently used in the computer graphics field for applications such as the display of images generated through x-ray crystallography, computer tomography, positron emission tomography and computational fluid dynamics.
Volume data is represented by a three dimensional array of volume elements referred to as "voxels". Associated with each voxel are three integer coordinates representing its location in volume space and at least one integer value called its density, representing some property at the location, e.g. temperature or composition, which is not directly related to rendering attributes. On the other hand, geometric data is represented by an x, y, z coordinate position and associated rendering attributes such as color. Geometric data unlike volume data, may be easily rendered for display because the data provides the rendering information necessary to display a geometric image; volume data contains information related to the volume object itself.
Therefore, in order to display volume data, the volume data must be translated out of volume space into a format compatible with the display system space. There are basically two techniques to render volumes on a computer graphics display: geometric and volumetric. In the geometric approach the volume data is fitted to geometric primitives which produces a model comprises of those primitives. In the volumetric approach the volume is rendered directly using either multiplanar reprojection or raycasting techniques.
Fuchs, Optimal Surface Reconstruction for Planar Contours, CACM 20 (1977), describes a geometric algorithm for rendering surfaces contained in volumetric data by reconstructing a 3-dimensional surface from a set of contours drawn on serial slices through the volume. The contours are commonly obtained using semi-automatic edge following routines, which are then tiled using geometric primitives such as triangles, polygons, or bi-cubic patches. These primitives form 3-D polygonal models which can be rendered using conventional techniques. A similar technique for surface reconstruction is described in Cline et al., U.S. Pat. No. 4,729,098. However, the extraction of surface contours frequently requires operator intervention. Large numbers of polygons are required to retain detail. In addition, because the volume data is now represented only by the surface data of the volume; the raw volume data is lost and partial surfaces or objects cannot be displayed.
In an effort to retain surface detail at the voxel level the Cuberille method was developed (Gordon, Image Space Shading of 3-Dimensional Objects, Computer Vision Graphics and Image Processing 29, 377-393 (1985)). This technique creates a binary volume compressed for rendering efficiency representing a surface boundary. The faces of the voxels are rendered as shaded polygons. This technique does not allow for semi-transparent or partial surfaces. Another geometric algorithm, known as Marching Cubes, calculates the intersection of the surface with the voxel cube and generates triangles that give a highly detailed surface approximation. See, Lorenson, et. al. Marching Cubes: A High Resolution 3-D Surface Construction Algorithm, Computer Graphics, Siggraph 1987 Proceedings, pages 163-169 (July 1987). Even more detail is provided by the dividing cubes algorithm, which represents the boundary as a set of points. See Cline, et. al., Two Algorithms For The Reconstruction Of Surface From Tomograms, Medical Physics June 1988 and Cline, U.S. Pat. No. 4,719,585.
However, these methods provide for the surface extraction of the volume; the raw volume data is not maintained. Therefore, any further interaction with the raw volume data is not possible because only the volume surface information is retained. Thus, such functions as partial volumes, transparency, translucency and interaction with a volume, such as picking (i.e., reading data values from volumes or writing data values from volumes) and the imposition of a geometric object on the volume, cannot be performed.
In the compositing technique, the volume data is preprocessed by classifying each voxel according to various rendering attributes such as color, opacity and texture thereby creating a multiplicity of volume representations. The different volume representations are then combined to form a single volume representation to be rendered on a display device. See Drebin, et. al., Volume Rendering, Computer Graphics Siggraph proceedings, pages 65-74, August 1988; LeVoy, Display Of Surfaces From Volume Data, IEEE Computer Graphics and Applications (May 1988) and Goldwasser, et. al., U.S. Pat. No. 4,737,921. However, this technique does not provide for a continuous mapping function. Thus, if the output image to be rendered is significantly larger than the original volume data, significant aliasing occurs.
Raycasting is a simple way of direct voxel rendering. Roth, Raycasting For Modeling Solids, Computer Graphics and Image Processing 18, pages 109-144; Sabella, A Rendering Algorithm For Visualizing 3-D Scalar Fields, Computer Graphics Siggraph 1988 Proceedings, pages 51-55, August 1988; Upson et al., V-Buffer Visible Volume Rendering, Computer Graphics, Siggraph 1988 Proceedings, pages 59-64, August 1988. In the raycasting technique a ray is emitted at each pixel through the volume along the view-vector. The values determined along the ray are combined to be a single value and displayed on the display output. There have been many algorithms developed to determine the output rendered by the ray. For example, the additive reprojection algorithm produces an x-ray like image by averaging the intensities of volume points along the ray. Another raycasting technique assigns color and opacity to density ranges allowing the volume to be viewed as a composition of translucent gels. (See Schlusselberg, et al., 3-Dimensional Display Of Medical Image Volumes, Proceedings of the NCGA, March 1986). Kjiya, et al., Raytracing Volume Densities, Computer Graphics, Siggraph 1984 Proceedings, pages 165-173, describes true raytracing where additional rays are spawned at surface boundaries for the calculation of intersurface reflectance properties. In practice, however, true raytracing has not been used because it is computationally intensive and expensive. In the multiplanar reprojection technique, one or more planes are moved through a volume displaying the density values mapped to some coloring function. However, this technique, like raycasting, is cumbersome and computation intensive and requires additional renderings for different perspectives.